BRPI1001274B1

BRPI1001274B1 - método para tratar entrada ou saída para ou do um ou mais dispositivos de armazenamento/de mídia, sistema para tratar entrada/saída, e, meio de armazenamento legível por computador

Info

Publication number: BRPI1001274B1
Application number: BRPI1001274A
Authority: BR
Inventors: R Thaler Andrew
Original assignee: Sony Computer Entertainment America Llc
Priority date: 2009-10-26
Filing date: 2010-10-14
Publication date: 2020-02-04
Also published as: CN102171647A; KR101188472B1; EP2353079A1; US8412856B2; EP2353079B1; EP2353079A4; CN103123595A; KR20110074489A; US20110099204A1; CN103123595B; JP5292473B2; BRPI1001274A2; WO2011053463A1; CN102171647B; JP2012505490A

Abstract

método para tratar entrada ou saída para ou do um ou mais dispositivos de armazenamento/de mídia, sistema para tratar entrada/saída, e, meio de armazenamento legível por computador uma solicitação de i/o entrante é recebida proveniente de uma aplicação sendo executada em um processador. uma estrutura em árvore incluindo processador-executáveis instruções de processador executáveis define uma ou mais camadas de processamento associadas com a solicitação de i/o. as instruções dividem os dados na solicitação de i/o em um ou mais agrupamentos de dados em cada uma da uma ou mais camadas de processamento. cada instrução tem uma dependência de dados associada para uma ou mais correspondentes instruções em uma camada anterior. as instruções são classificadas em uma ordem de processamento determinando uma localização de cada agrupamento de dados e as dependências de dados entre agrupamentos de dados de diferentes camadas de processamento. uma ou mais instruções são inserida em uma programação que depende de pelo menos, parcialmente da ordem de processamento. a solicitação de i/o é atendida executando as instruções de acordo com a programação com o processador de acordo com a ordem de processamento.

Description

“MÉTODO PARA TRATAR ENTRADA OU SAÍDA PARA OU DO UM OU MAIS DISPOSITIVOS DE ARMAZENAMENTO/DE MÍDIA, SISTEMA PARA TRATAR ENTRADA/SAÍDA, E, MEIO DE ARMAZENAMENTO LEGÍVEL POR COMPUTADOR”

REIVINDICAÇÃO DE PRIORIDADE [001] Este pedido reivindica o benefício da prioridade do pedido provisório dos US de número 61/255.013, para Andrew R. Thaler, com o título de FILE 1NPUT/OUTPUT SCHEDULING USING IMMEDIATE DATA CHUNKING, depositado em 26 de outubro de 2009, as inteiras divulgações das quais são incorporadas aqui para referência.

[002] Este pedido reivindica o benefício da prioridade do pedido provisório dos US de número 12/902,768, to Andrew R. Thaler, com o título de F1LE 1NPUT/OUTPUT SCHEDUL1NG US1NG 1MMED1ATE DATA CHUNK1NG, depositado em 12 de outubro de 2010, as inteiras divulgações das quais são incorporadas aqui para referência.

CAMPO DA INVENÇÃO [003] Modalidades desta invenção são relacionadas a jogos de computador e aplicações relacionadas e mais especificamente ao gerenciamento de arquivo de entrada/saída (I/O) gerenciamento em jogos de computador e aplicações relacionadas.

FUNDAMENTOS DA INVENÇÃO [004] Muitas aplicações de aplicação de software, tal como jogos de vídeo, incluem um programador de arquivo de entrada/saída (I/O) para fazer acesso de mídia dentro de uma aplicação mais eficiente e confiável. Um sistema de arquivo de I/O (FIOS) é uma camada de middleware para acessar arquivos com várias partes incluindo um programador e camadas de I/O opcionais. O programador é tipicamente projetado para de modo ótimo ordenar solicitações de I/O tal que elas terminam no tempo mais curto possível sujeito a prazo arbitrário e restrições de prioridade. As camadas de

Petição 870190110896, de 30/10/2019, pág. 9/92 / 39 filtro podem fornecer serviços adicionais tais como descompressão ou armazenamento em cache.

[005] Muitos diferentes componentes de jogo requerem acesso de

I/O para arquivos na mídia de armazenamento. Componentes de áudio carregam arquivos de áudio; mecanismos de execução de jogo carregam definições de níveis; componentes gráficos carregam mapas e modelos; componentes de filme carregam arquivos áudio visuais; e subsistemas carregam grande arquivos de WAD. A mídia pode ser mídia de entrega de jogo tal como discos ópticos (disco de mídia universal (UMD), disco compacto (CD), disco de vídeo digital (DVD), disco de Blu-Ray, etc.), mídia de armazenamento intermediário tal como discos rígidos, ou outros tipos de mídia conforme as plataformas evoluem [006] Uma única aplicação tal como um jogo de vídeo, tipicamente tem múltiplos componentes, cada componente tendo seus próprios requisitos de I/O. Alguns requerem acesso seqüenciado para mídia, onde o sistema de I/O seqüencia dados no arquivo para o componente assim o componente pode apresentar os dados seqüenciados para o jogador do jogo. Por exemplo, um componente de áudio tipicamente seqüencia um arquivo de áudio para executar trilhas de som; um componente de filme seqüencia conteúdo de áudio e vídeo para reproduzir um filme para o tocador. Outros componentes necessitam somente de acesso não seqüenciado onde eles recuperam dados do arquivo em porções, aqui referido como agrupamentos de dados, para o componente processar. Embora esses componentes não requeiram fluxo de dados estável de modo a processar, o tempo da entrega dos agrupamentos de dados é freqüentemente crucial. Se uma aplicação não recebe dados quando é necessário, o desempenho pode sofrer.

[007] Correntemente, operação de compor agrupamento de dados (i.e., quebrar dados para uma solicitação de I/O em porções/agrupamentos de dados) ocorre durante execução da solicitação de I/O. Dependências de dados

Petição 870190110896, de 30/10/2019, pág. 10/92 / 39 entre agrupamentos de dados não são determinados antes que a execução, e isto acarreta ineficiências no processamento de solicitações de I/O. Por exemplo, uma dada solicitação de solicitação de I/O pode requerer dados que necessitam ser ambos, descomprimidos e sem criptografia. Antes que a transferência. O sistema de I/O pode requerer que descriptografia de um dado agrupamento de dados ocorra antes que a descompressão, mas diferentes tamanhos de agrupamento de dados podem estar associados com descriptografia e descompressão. Por exemplo, os tamanhos de agrupamento de dados associados com descriptografia podem tem um valor fixo tal como 64 Kilobytes, ao passo que os tamanhos de agrupamento de dados associados com descompressão podem ser variáveis. Assim sendo, sem determinar a dependência dos dados entre os agrupamentos de dados sendo destituídos da criptografia e os agrupamentos de dados sendo descomprimido, um arquivo inteiro precisa ser destituído da criptografia antes do arquivo possa ser descomprimido, mais propriamente do que iniciar descompressão de um dado agrupamento de dados uma vez que os necessários agrupamentos de dados sem criptografia foram processados.

[008] De forma similar, uma determinada solicitação de I/O que requer dados a serem recuperados a partir de múltiplas fontes de mídia pode ser processada de modo ineficiente com a forma corrente de compor agrupamento de dados durante execução. Sem determinar as dependências de dados entre agrupamentos de dados antes que a execução, um dispositivo de mídia pode ficar ocioso enquanto dados de um outro dispositivo de mídia estão sendo processado, quando é teoricamente possível para dados a partir de ambos dispositivos de mídias a serem processados simultaneamente. Isto finalmente desacelera a funcionalidade de um jogo de vídeo ou outra aplicação.

[009] Ainda mais, jogos de vídeo freqüentemente efetuam uma quantidade considerável de I/O. Eventos de jogo são freqüentemente

Petição 870190110896, de 30/10/2019, pág. 11/92 / 39 orientados no tempo com prazos que precisam ser satisfeitos. Por exemplo, se um jogador está viajando do ponto A para o ponto B, o jogo necessita ter os arquivos para dados associados com o ponto B carregado antes do jogador chega lá. Componentes de jogo podem usar primitivas de I/O de nível baixo para recuperar dados da mídia, mas essas primitivas não tratam contenção de dispositivo quando múltiplos componentes requerem dados do mesmo dispositivo ao mesmo tempo. Solicitações de I/O emperradas pode interromper seqüenciamento de fluxo de dados ou proibir agrupamentos de dados de dados críticos de chegar a um componente quando necessário.

[0010] Porque componentes de aplicação tipicamente não estão cientes das atividades de I/O cada um do outro, suas solicitações de I/O freqüentemente resultam em padrões de I/O altamente ineficiente com uma quantidade substancial de procura extra(pesquisas de dados para trás e para frente). Conforme os jogos ficam maiores, procura extra e recuperação de dados ineficiente aumentam.

[0011] É dentro deste contexto que modalidades da presente invenção surgem.

DESCRIÇÃO BREVE DOS DESENHOS [0012] Os ensinamentos da presente invenção podem ser prontamente entendidos considerando a seguinte descrição detalhada em conjunto com os desenhos anexos, nos quais:

FIG. 1 é um diagrama em bloco de um sistema que implementa um sistema de arquivo de I/O (FIOS) de acordo com uma modalidade da presente invenção.

FIG. 2 é um diagrama em bloco de um sistema alternativo que implementa um FIOS de acordo com uma modalidade alternativa da presente invenção.

FIG. 3 é um diagrama em bloco do software do sistema de arquivo de entrada/saída (FIOS) de acordo com uma modalidade da presente

Petição 870190110896, de 30/10/2019, pág. 12/92 / 39 invenção.

FIG. 4 é um fluxograma de dados ilustrando um fluxo de operações em um FIOS de acordo com uma modalidade da presente invenção.

FIG. 5 é um fluxograma ilustrando um exemplo de um programador de software usado em um FIOS de acordo com uma modalidade da presente invenção.

DESCRIÇÃO DAS MODALIDADES ESPECÍFICAS [0013] Embora a seguinte descrição detalhada contem muitos detalhes específicos para o propósito de ilustração, qualquer um de qualificação simples na técnica vai apreciar que muitas variações e alterações para os seguintes detalhes estão dentro do escopo da invenção. Conseqüentemente, modalidades da invenção descritas abaixo são estabelecidas sem qualquer perda de generalidade para, e sem impor limitações, a invenção reivindicada.

[0014] Modalidades da presente invenção podem ser implementadas em torno de um sistema de arquivo de I/O (FIOS) que fornece uma camada centralizada por onde todos os I/O de um sistema passam. O FIOS pode incluir instruções que criam uma estrutura em árvore para processamento ótimo de cada solicitação de I/O individual, e instruções que programam solicitações de I/O e determinam uma ordem na qual atender as solicitações de I/O mais eficientemente.

[0015] Por meio de exemplo, um sistema implementado por computador 100 pode ser configurado para implementar um sistema de arquivo de I/O (FIOS) de acordo com uma modalidade da presente invenção conforme mostrado na FIG. 1. Por meio de exemplo, e sem perda de generalidade, o sistema 100 pode ser implementado como um computador pessoal, console de jogo de vídeo, dispositivo de jogo portátil, telefone celular, assistente digital pessoal, ou outro dispositivo digital, adequado para praticar as modalidades da invenção. O sistema 100 pode incluir uma unidade de processamento 105 e uma memória principal 106 acoplada à unidade de

Petição 870190110896, de 30/10/2019, pág. 13/92 / 39 processamento 105. A CPU 105 pode ser configurada para executar aplicações de software e, opcionalmente, um sistema operacional. Algumas modalidades da presente invenção podem tirar vantagem de certos tipos de arquitetura de processador na qual a CPU 105 inclui um processador principal 105A e um processador auxiliar 105B tendo sua própria memória local associada 106B. Um exemplo, dentre outros de tal uma arquitetura de processador é um Processador Célula. Um exemplo de uma arquitetura de Processador Célula é descrito em detalhe, e.g., em Cell Broadband Engine Architecture, direitos de cópia da International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation 8 de agosto de 2005 uma cópia da qual pode baixada em http:// cell.scei.co.jp/, da qual os conteúdos inteiros são aqui incorporados para referência.

[0016] A memória principal 106 pode armazenar aplicações e dados para uso pela CPU 105. A memória principal 106 pode ser na forma de um circuito integrado, e.g., RAM, DRAM, ROM, e o similar. Um programa de computador 101 pode ser armazenado na memória 106 na forma de instruções que podem ser executados no processador 105. As instruções do programa 101 podem ser configuradas para implementar dentre outras coisas, um sistema de arquivo de input/output (FIOS) tendo certo recursos descritos a seguir. A memória 106 pode conter filas de I/O 101Q, e.g., na forma de pilhas ou filas para solicitações de I/O livres, completadas, emitidas, programadas e de entrada que são usadas pelos programas de FIOS 101. Exemplos de tais filas também são descritos abaixo.

[0017] Por meio de exemplo, o programa do FIOS 101 pode incluir instruções para a) receber uma solicitação de I/O entrante envolvendo o dispositivo de mídia 118 da aplicação 103, b) criar a estrutura em árvore configurada para formar uma ordem ótima de processamento para a solicitação de I/O determinando a localização e dependências de dados de

Petição 870190110896, de 30/10/2019, pág. 14/92 / 39 agrupamentos de dados (i.e. porções) de dados a serem transferidos, c) inserir a solicitação de I/O entrante em uma programação embutida na memória 106, onde a posição da solicitação de I/O entrante dentro da programação depende pelo menos, parcialmente na ordem de processamento da estrutura em árvore e d) implementar a solicitação de I/O de acordo com a programação e estrutura em árvore.

[0018] O sistema cliente 100 pode também incluir bem conhecidas funções de suporte 110, tal como elementos de entrada e saída (I/O) 111, fontes de fornecimento de energia (P/S) 112, um relógio (CLK) 113, e uma cache 114. O dispositivo do cliente 100 pode ainda incluir um dispositivo de cache 115 tal como um mecanismo de disco rígido que fornece armazenamento não volátil para aplicações e dados. O dispositivo de cache 115 pode ser usado, dentre outras coisas, para armazenamento de arquivos temporariamente ou a longo prazo 116 recuperados de um dispositivo de mídia mais baixo 118. Arquivos 116 no dispositivo de cache 115 pode adicionalmente vir de fontes outras do que o dispositivo de mídia mais baixo 118. Por exemplo, os arquivos 116 podem incluir, mas não são limitados à, arquivos do sistema operacional, arquivos temporários criados por uma aplicação, dados de usuários tal como fotos/áudio/vídeo, conteúdo baixado, e mais. Por meio de exemplo, o dispositivo de armazenamento 115 pode ser um mecanismo de disco fixo, mecanismo de disco removível, dispositivo de memória flash, ou mecanismo de fita. O dispositivo de mídia mais baixo 118 pode ser um mecanismo de disco óptico de alta capacidade, e.g., um mecanismo de CD-ROM drive, mecanismo de DVD-ROM, mecanismo de disposto versátil digital de alta definição (HD-DVD), um mecanismo de disco de Blu-Ray, um mecanismo de UMD, ou outros dispositivos de armazenamento óptico. Arquivos pré-busca dos 116 a partir do dispositivo de mídia 118 podem ser temporariamente armazenados no depósito 115 em um cache de hardware para carga rápida na memória 106.

Petição 870190110896, de 30/10/2019, pág. 15/92 / 39 [0019] Um ou mais dispositivo de entrada de usuários 120 pode ser usado para comunicar entradas de usuário a partir de um ou mais usuários para o sistema 100. Por meio de exemplo, um ou mais dos dispositivos de entrada de usuário 120 podem ser acoplados ao dispositivo do cliente 100 através dos elementos de I/O 111. Exemplos de dispositivos de entrada 120 adequados incluem teclados, mouses, joysticks, almofadas de toque, telas de toque, canetas de luz, câmeras fixas ou de vídeo, e/ou microfones. O dispositivo do cliente 100 pode incluir uma interface de rede 125 para facilitar comunicação através de uma rede de comunicações eletrônicas 127. A interface de rede 125 pode ser configurada para implementar comunicação com fio ou sem fio sobre redes de área local e redes de área ampla tal como a Internet. O sistema 100 pode enviar e receber dados e/ou solicitações para arquivos através de um ou mais pacotes de mensagens 126 sobre a rede 127.

[0020] O sistema pode ainda compreender um subsistema de gráficos 130, que pode incluir a unidade de processamento de gráficos (GPU) 135 e memória de gráficos 140. A memória de gráfico 140 pode incluir uma memória de exibição (e.g., uma área de armazenamento de quadro) usada para armazenar dados de elemento mínimo de imagem para cada elemento mínimo de imagem de uma imagem de saída. A memória de gráficos 140 pode ser integrada no mesmo dispositivo que a GPU 135, conectado com um dispositivo separado da GPU 135, e/ou implementado dentro da memória 106. Dados de elemento mínimo de imagem podem ser fornecidos para a memória de gráficos 140 diretamente a partir da CPU 105. Alternativamente, a CPU 105 pode fornecer a GPU 135 com dados e/ou instruções definindo as imagens de saída desejadas, a partir das quais a GPU 135 pode gerar dados de elemento mínimo de imagem de uma ou mais imagens de saída. Os dados e/ou instruções definindo as imagens de saída desejadas podem ser armazenadas na memória 106 e/ou memória de gráficos 140. Em uma modalidade, a GPU 135 pode ser configurada com capacidades de produção

Petição 870190110896, de 30/10/2019, pág. 16/92 / 39 de 3D para gerar dados de elemento mínimo de imagem para emitir imagens a partir das instruções e dados definindo parâmetros de geometria, iluminação, sombreamento, textura, movimento, e/ou câmera para uma cena. A GPU 135 pode ainda incluir um ou mais unidades de execução programáveis capazes de executar programas de sombreamento.

[0021] O subsistema de gráficos 130 pode periodicamente emitir dados de elemento mínimo de imagem para uma imagem a partir da memória de gráficos 140 para ser exibida em um dispositivo de exibição de vídeo 150. O dispositivo de exibição de vídeo 150 pode ser qualquer dispositivo capaz de exibir informação visual em resposta a um sinal do sistema 100, incluindo visores de CRT, LCD, plasma, e OLED. O sistema de computador 100 pode fornecer ao dispositivo de exibição 150 um sinal analógico ou digital. Por meio de exemplo, o visor 150 pode incluir um tubo de raio catódico (CRT) ou tela de painel plana que exibe texto, numerais, símbolo gráficos ou imagens. Em adição, o visor 150 pode incluir um ou mais alto-falantes de áudio que produzem sons audíveis ou por outro lado detectáveis. Para facilitar geração de tais sons, o dispositivo do cliente 100 pode ainda incluir um processador de áudio 155 adaptado para gerar saída de áudio analógico ou digital a partir das instruções e/ou dados fornecido pela CPU 105, memória 106, e/ou depósito 115.

[0022] Os componentes do sistema 100, incluindo a CPU 105, memória 106, funções de suporte 110, dispositivo de armazenamento de dados 115, dispositivo de mídia 118, dispositivo de entrada de usuários 120, interface de rede 125, e processador de áudio 155 pode ser de modo operável, conectado cada um ao outro através de uma ou mais barras de comunicação de dados 160. Esses componentes podem ser implementados em hardware, software, firmware, ou alguma combinação de dois ou mais deles.

[0023] Algumas modalidades da presente invenção podem tirar vantagem de uma arquitetura de processador célula ou arquitetura de

Petição 870190110896, de 30/10/2019, pág. 17/92 / 39 processador similar. FIG. 2 ilustra um processador célula 200 configurado para implementar um FIOS de acordo com uma modalidade da presente invenção. O processador célula 200 inclui uma memória principal 202, um único elemento de processador de energia (PPE) 204, e oito elementos de processador sinérgico (SPE) 206. Por meio de exemplo, o PPE 204 pode incluir uma Unidade de Processador de Energia de PC de 64 bits (PPU) com pequenos caches associados. Algumas implementações, e.g., sistemas condizentes com CBEA podem incluir uma unidade de extensão de vetor de multimídia no PPE 204. O PPE 204 pode ser uma unidade de processamento de propósito geral que pode acessar recursos de gerenciamento de sistema (tal como tabelas de proteção de memória). Recursos de hardware podem ser mapeados de forma explícita para um espaço de endereço real como visto pelo PPE 204. Por conseguinte, o PPE 204 pode endereçar qualquer desses recursos diretamente usando um valor de endereço eficaz apropriado. Uma função primária do PPE 204 é o gerenciamento e alocação de tarefas para os diferentes SPEs 206. A PPU pode executar instruções codificadas de um programa de programa de FIOS 101.

[0024] Os SPEs 206 são unidades computacionais menos complexas do que o PPE 204, nas quais elas não necessitam efetuar quaisquer funções de gerenciamento do sistema. Cada SPE 206 inclui uma unidade de processador, algumas vezes referida como uma unidade de processador sinérgico (SPU) e um depósito local associado (LS). O SPE 206 pode geralmente ter uma instrução única, capacidade de múltiplos dados (SIMD) e tipicamente dados de processo e iniciar qualquer transferência de dados requeridos (sujeita para ter propriedades de acesso estabelecidas pelo PPE 204) de modo a efetuar suas tarefas alocadas. Um SPE 206 pode armazenar em seu depósito local instruções 207 que implementam porções do programa de FIOS 101. O propósito do SPE 206 é permitir aplicações que requerem uma maior densidade da unidade computacional e pode eficazmente usar o conjunto de

Petição 870190110896, de 30/10/2019, pág. 18/92 / 39 instrução fornecido. Embora 8 SPEs sejam mostrados neste exemplo, o processador célula 200 pode ser configurado com qualquer número de SPEs. Com relação à FIG. 2, a memória 202, PPE 204, e SPE 206 pode comunicar cada um com o outro e com dispositivo de I/O 208 sobre uma barra de comunicação de interconexão de elementos do tipo anel 210. A memória 202 pode ser acessada pelo PPE 204 e SPEs 206 através de um controlador de interface de memória (MIC).

[0025] A memória 202 pode conter filas de I/O 203, e.g., filas entrantes, agendadas, emitidas, completadas, livres e pré-busca das conforme descrito a seguir. A memória 202 pode também contem porções de um programa de FIOS 101 tendo recursos em comum com o programa de FIOS 101 descrito aqui. O PPE 204 pode incluir um cache interno (L1) e cache externo (L2). O PPE pode armazenar porções do programa de FIOS 101 em seu cache interno (L1). O programa de FIOS 101 e as instruções de transferência de arquivo implementadas no 207, ou porções delas, também podem ser armazenados na memória 202 para acesso pelo SPE 206 e PPE 204 quando necessário.

[0026] Por meio de exemplo, o programa de FIOS 101 pode incluir uma pilha de mídia 300 para facilitar a interface com hardware tal como o dispositivo de armazenamento 115 ou dispositivo de mídia 118 conforme mostrado na FIG.3. A pilha de mídia 300 pode incluir uma camada de estrutura em árvore 301, um programador 303, uma ou mais camadas de filtro de mídia 305, uma camada de dispositivo mídia 307, uma camada de leitura de sistema de arquivo de processador (FS) 309, e uma camada de hardware 311.

[0027] A camada de estrutura em árvore 301 cria um mapa para facilitar processamento ótimo dos dados associados com uma solicitação de I/O individual a ser transferida. Inicialmente, uma estrutura em árvore 313 é criada tal que define uma ou mais camadas de processamento 306 (e.g.,

Petição 870190110896, de 30/10/2019, pág. 19/92 / 39 descriptografia, descompressão, de desarquivamento, etc.) associadas com uma determina solicitação de I/O. Os dados a serem transferidos ou recebidos por solicitação de I/O são processados em cada camada 306 da estrutura em árvore 313 e a estrutura em árvore 313 é configurada para não começar uma subseqüente camada de processamento até bastante dos dados na camada anterior foi processada. A estrutura em árvore 313 então quebra os dados a serem transferidos ou recebidos em um ou mais agrupamentos de dados 302 em cada uma da uma ou mais camadas de processamento 306. Os agrupamentos de dados 302 associados com uma particular camada de processamento 306 têm um ou mais tamanhos correspondendo àquela particular camada de processamento 306. Os tamanhos de agrupamento de dados para diferentes camadas podem ser diferentes. A estrutura em árvore 313 forma uma ordem ótima de processamento dos agrupamentos de dados para as diferentes camadas determinando a localização de cada agrupamento de dados 302 e as dependências de dados 304 entre agrupamentos de dados 302 de diferentes camadas de processamento 306.

[0028] Por meio de exemplo, e não por meio de limitação, uma solicitação de I/O pode incluir receber dados que são criptografados e comprimidos. Inicialmente a estrutura em árvore cria duas camadas de processamento, incluindo uma camada de descriptografia e um a camada de descompressão de modo executar a solicitação de I/O. Neste exemplo, os dados a serem transferidos necessitam ser descomprimido antes de poderem ser recebido pela aplicação e se necessita retirar a criptografia dos dados a serem transferidos antes de poderem ser descomprimido. A camada de estrutura em árvore 301 quebra os dados a serem transferidos em agrupamentos de dados (i.e., porções dos dados) dependendo da camada de processamento. Em particular, a estrutura em árvore 301 gera instruções para quebrar os dados em agrupamentos de dados com tamanhos que são selecionados tal que porções de dados podem ser processados, de forma

Petição 870190110896, de 30/10/2019, pág. 20/92 / 39 simultânea, mais propriamente do que tendo de esperar por uma parte inteira de dados para terminar um nível de processamento antes que um próximo nível de processamento possa começar. Cada instrução para um dado agrupamento de dados pode definir o agrupamento de dados através de um nome de caminho, um offset, e um comprimento.

[0029] Por exemplo, descriptografia pode ser realizada em um tamanho de agrupamento de dados de 64K fixo, e assim a camada de estrutura em árvore 301 pode quebrar os dados em agrupamentos de dados de 64K para descriptografia. Descompressão, contudo, pode ser processada em tamanhos variáveis, e assim a camada de estrutura em árvore pode quebrar os dados em agrupamentos de dados de tamanhos variáveis para descompressão.

[0030] O processo de descompressão (transformação de desarquivamento) pode pegar um agrupamento de dados comprimido e sem criptografia de tamanho variável e o descomprime para um agrupamento de dados de tamanho fixo. A camada de estrutura em árvore 301 ou camadas de filtro de mídia 305 podem ser configuradas para determinar que agrupamentos de dados de tamanho variável dos dados comprimidos e sem criptografia descomprimem para agrupamentos de dados de tamanho fixo sem primeiro ter de descomprimi-los. Para facilitar determinação do comprimento variável do agrupamento de dados criptografado na hora de compor agrupamento de dados, as camadas de filtro de mídia 305 (que finalmente determina que agrupamentos de dados são criados) podem armazenar na RAM qualquer que seja a informação que eles necessitam para computar o tamanho e localização de um dado agrupamento de dados. Por exemplo, para um arquivo psarc do FIOS, uma camada de desarquivamento pode manter a tabela de conteúdo (TOC) do arquivo psarc na RAM. A TOC pode conter uma tabela que lista o tamanho de cada bloco comprimido no arquivo, e a camada de mídia desarquivamento pode derivar a localização do bloco a partir daquele. Assim, eficazmente, o desarquivamento é capaz de traduzir a solicitação entrante para

Petição 870190110896, de 30/10/2019, pág. 21/92 / 39 um bloco de dados não comprimidos na solicitação para o correspondente bloco de dados comprimidos. A única informação que o desarquivamento necessita para fazer esta transformação é o TOC, que ele tem na RAM. O desarquivamento não necessita eficazmente ler ou descomprimir qualquer dados para criar o nó da árvore.

[0031 ] Porque os tamanhos dos agrupamentos de dados da camada de descriptografia e os tamanhos dos agrupamentos de dados da camada de descompressão não se alinham, um dado agrupamento de dados sem criptografia pode não ser sempre descomprimido imediatamente. Em vez disso, mais do que um agrupamento de dados da camada de descriptografia pode necessitar retirar a criptografia antes que um agrupamento de dados de camada de descompressão possa começar a ser descomprimido. Uma ordem ótima de processamento é então estabelecida determinando a localização dos agrupamentos de dados associados com cada camada e determinando as dependências de dados entre agrupamentos de dados de diferentes camadas. Desta maneira, mais propriamente do que esperar por uma inteira camada de processamento para completar antes que a subseqüente camada de processamento possa começar, uma subseqüente camada de processamento pode começar tão logo os necessários agrupamentos de dados de dados na camada anterior sejam processados (e.g., descompressão de um dado agrupamento de dados pode começar uma vez que os necessários agrupamentos de dados a nível de descriptografia terminaram de retirar a criptografia).

[0032] Ocasionalmente, uma solicitação de I/O pode requerer dados a serem recuperado a partir de mais do que dispositivo de mídia/de armazenamento. Assim sendo, determinando dependência de dados antes que a execução, processamento de uma solicitação de I/O com dados de múltiplos dispositivos de armazenamento/de mídia pode ser feito, de forma simultânea, mais propriamente do que tendo um dispositivo de mídia/de armazenamento

Petição 870190110896, de 30/10/2019, pág. 22/92 / 39 ocioso enquanto o outro dispositivo de mídia/de armazenamento está processando sua porção da solicitação de I/O. Por meio de exemplo, e não por meio de limitação, uma determinada solicitação de I/O pode requerer recuperação de dados de ambos, um disco rígido (HD) e um dispositivo de mídia Blu-Ray. Ao delinear as dependências de dados para a determinada solicitação de I/O, pode ser determinado que exatamente é necessário do HD e o que exatamente é necessário do Blu-Ray. Desta maneira, quando a estrutura em árvore determina ser permitido, os dados de ambos os dispositivos podem ser processados, de forma simultânea, mais propriamente do que tendo um dispositivo ocioso enquanto dados do outro dispositivo estão sendo processados.

[0033] Uma vez que a estrutura em árvore 313 foi criada, o programador 303 então pode inserir as instruções da estrutura em árvore que compõe a solicitação de I/O entrante em uma programação embutida na memória. A posição de uma dada instrução dentro da programação depende pelo menos, parcialmente na ordem de processamento associada com a estrutura em árvore 313.

[0034] Se duas ou mais diferentes solicitações de I/O na programação contêm estruturas em árvore 313 similares, essas solicitações de I/O pode ser intercaladas tal que mais do que um solicitação pode ser processada ao mesmo tempo. Isto pode melhorar a eficiência de cumprimento das solicitações de I/O porque solicitações de I/O relacionadas podem ser completada ao mesmo tempo ou com tempos se sobrepondo, mais propriamente do que esperando cada solicitação de I/O terminar o processamento antes de começar ao próximo processamento. Por exemplo, em algumas modalidades, uma ou mais instruções de outras solicitações de I/O que forma intercaladas com as instruções da estrutura em árvore 313 podem ser executadas em paralelo com execução das instruções da estrutura em árvore 313.

Petição 870190110896, de 30/10/2019, pág. 23/92 / 39 [0035] Por meio de exemplo, e não por meio de limitação solicitações de I/O podem ser intercaladas se o programador 303 determina que as solicitações serão atendidas mais rápido se elas estão intercaladas. Isto pode ser ilustrado pelos próximos dois exemplos.

[0036] De acordo com um primeiro exemplo, suponha que duas leituras corrigidas por patch estão sendo executadas simultaneamente. O arquivo A necessita cinco agrupamentos de dados: (A1) (A2) (P1) (A3) (P2). O arquivo B necessita quatro agrupamentos de dados: (B1) (P3) (B2) (B3). P neste caso representa um arquivo de patch, e A e B são os arquivos de dados originais. O esquema no disco pode parecer com este:

... (A1) (A2) (A3)... (B1) (B2) (B3).............(P1) (P2)...

[0037] Note que por causa da proximidade dos arquivos no disco, o programador 303 pode determinar que maneira mais rápida de terminar ambas leituras com pesquisa mínima pode ser, para intercalar as solicitações lendo A1-A3 primeiro, então B1-B3, e então P1-P3.

[0038] De acordo com um segundo exemplo suponha que o programador 303 programou uma primeira solicitação de leitura e uma segunda solicitação de leitura de baixa latência e alta prioridade (e.g., uma solicitação de áudio) é programada. O FIOS 101 pode iniciar o trabalho nos agrupamentos de dados a partir da primeira leitura como representado na tabela I abaixo. Na tabela I, os agrupamentos de dados se movem para a esquerda a o longo do tempo, eles iniciam na fila, se movem para execução e finalmente terminam completamente.

TABELA I feito | executando | na fila

I I (Al) (A2) (A3) (A4) (A5) (A6) (A7) (A8) [0039] Após a execução de A3 ter iniciado, a aparência da fila pode parecer como representado na tabela II abaixo:

Petição 870190110896, de 30/10/2019, pág. 24/92 / 39

TABELA II feito | executando | na fila (Al) (A2) I (A3) | (A4) (A5) (A6) (A7) (A8) [0040] Suponha agora quem um áudio thread vem e de repente quer carregar (B1) e (B2). Se leitor de áudio solicita atendimento imediato, o programador 303 pode colocar a leituras de (B1) e (B2) na frente da fila. A fila pode agora parecer conforme mostrado na tabela III abaixo:

TABELA III

Feito | executando | na fila (Al) (A2) | (A3) | (Bl) (B2) (A4) (A5) (A6) (A7) (A8) [0041] Finalmente quando a execução desta parte da fila está terminada pode ser visto que a I/O foi intercalada para as duas solicitações de leitura conforme mostrado na tabela IV.

TABELA IV feito | executando | na fila (Al) (A2) (A3) (Bl) (B2) (A4) (A5) (A6) (A7) (A8) | | [0042] A camada de dispositivo mídia 307 (algumas vezes chamada de camada de acesso de mídia) pode ser configurada para responder às solicitações de mídia recebidas a partir das camadas de filtro de mídia 305 acima, recuperando os dados solicitados, e então enviando sua resposta de volta para o topo da pilha 300.

[0043] As camadas de filtro de mídia 305 podem incluir, um executor de patch 322, uma camada de desarquivamento 308, uma camada de cache de RAM 310, uma camada de cache do programador 312, uma camada de sobreposição 314, uma camada de cache de catálogo 316, uma camada de criptografia/de descriptografia 318, e uma camada de compressão/de descompressão 320. Essas camadas de filtro de mídia 305 correspondem às camadas de processamento 306 associadas com a estrutura em árvore 313. Uma dada parte de dados associada com uma solicitação de I/O pode ter múltiplas camadas de processamento dependendo do número de camadas de filtro de mídia associado com os dados. O desarquivamento 308 pode ser usado para facilitar extração de arquivos ativos específicos a partir dos

Petição 870190110896, de 30/10/2019, pág. 25/92 / 39 arquivos comprimidos. A camada de cache de RAM 310 pode ser usada para implementar cache de dados, e.g., na memória principal. O cache programador 312 pode ser um cache de disco a disco para temporariamente armazenar dados de uma fonte mais lenta para um disco óptico. Como usado aqui, o termo “cache programador” se refere à armazenamento de dados temporário em um meio de armazenamento que é mais rápido para ter acesso do que o dispositivo de mídia. Não é necessário para todos os dados no cache programador 312 serem pré-busca dos; alguns podem ser busca dos sob demanda e copiados no cache. Por meio de exemplo, e não por meio de limitação, a camada de cache programador 312 pode utilizar o meio de cache para fornecer tal armazenamento temporário. No caso particular onde o meio de cache é um mecanismo de disco rígido (HDD), o cache programador 312 é algumas vezes referido como um HDD de cache.

[0044] O cache programador 312 pode ser mantido como um único arquivo ou como múltiplos arquivos. Em adição, o conteúdo do cache programador 312 não necessita ser arquivos completos. Um cache de múltiplos arquivos pode ser parcialmente liberado eliminado alguns dos arquivos individuais para de forma inteligente liberar espaço em disco quando necessário sem sacrificar muitos dados. Caches de arquivo único, ao contrário, tipicamente podem, somente ser truncados ou inteiramente eliminados. Caches de arquivo único podem fornecer maior desempenho do que caches de múltiplos arquivos já que um cache de múltiplos arquivos tipicamente requer adicional trabalho de contabilidade (dentro do próprio sistema de arquivo do hospedeiro), que pode requerer extra I/O.

[0045] A camada de sobreposição 314 pode ser usada para permitir sobreposição arbitrária de arquivos e diretorias no nível de sistema de arquivo discutido a seguir. A camada de cache de catálogo 316 pode ser usado para dados de cache que o O/S para um unidade de processador ou processador célula pode não apropriadamente armazenar em cache (e.g., existência de

Petição 870190110896, de 30/10/2019, pág. 26/92 / 39 arquivo, tamanho, e localização). A camada de criptografia/de descriptografia camada 318 pode ser usada para facilitar criptografia ou descriptografia de dados para transferência. A camada de compressão/descompressão 320 pode ser usada para facilitar compressão ou descompressão de dados para transferência.

[0046] Operação da camada de estrutura em árvore 301 e o programador 303 do programa de FIOS 101 podem ser entendidos com relação à FIG. 4, que é descrita abaixo. A partir de um ponto de vista do cliente, uma solicitação de I/O 403 pode ser atendida em uma maneira relativamente direta. Por exemplo, a thread 402 dentro de uma aplicação 401, tal como um jogo de vídeo pode solicitar I/O através do programa de FIOS 101 chamando uma função (e.g., readFile()). A função pode especificar uma prioridade para a solicitação de I/O 403 e um prazo no qual a solicitação 403 deve ser completada. A pilha de mídia do FIOS 300 então usa a camada de estrutura em árvore 301 para criar a estrutura em árvore 313 para a solicitação de I/O 403 que forma um mapa definindo um ordem ótima de processamento para aquela solicitação de I/O 403.

[0047] A estrutura em árvore inicialmente define os níveis de processamento 306 associados com uma determinada solicitação de I/O 403. Por exemplo, uma determinada solicitação de I/O 403 pode solicitar transferir dados a partir do processador para o dispositivo de mídia, onde os dados são necessários para serem comprimidos, criptografados, e arquivados. Nesta situação, a estrutura em árvore 313 vai definir três níveis 306 de processamento para a compressão, criptografia, e arquivamento dos dados associados com a solicitação de I/O 403. Uma determinada parte de dados precisa ser comprimida antes de ser criptografada, criptografada antes de ser arquivada, e arquivada antes de ser finalmente transferida para o dispositivo de mídia.

[0048] A estrutura em árvore 313 então quebra os dados a serem

Petição 870190110896, de 30/10/2019, pág. 27/92 / 39 transferidos em agrupamentos de dados 302 de acordo com o nível de processamento 306 (e.g., dados são quebrados em agrupamentos de dados de 64K ao nível de compressão, dados são quebrados em agrupamentos de dados de tamanhos variáveis no nível de criptografia, e dados são quebrados em agrupamentos de dados de 64K no nível de arquivamento). Os dados são quebrados em agrupamentos de dados 302, tal que porções de dados em qualquer determinado nível ou em diferentes níveis podem ser processados, de forma simultânea, mais propriamente do que tendo de esperar para todos os dados na solicitação terminem à nível de processamento 306 antes que o próximo nível de processamento 306 possa começar. Porque os agrupamentos de dados 302 de um nível de processamento 306 não necessariamente se alinham com os agrupamentos de dados 302 de um outro nível de processamento 306, dependências de dados 304 de agrupamentos de dados 302 correspondendo aos diferentes níveis de processamento 306 precisam ser mapeadas de modo a agilizar o processamento da solicitação de I/O 403. Por exemplo, um agrupamento de dados de nível de compressão determinado pode não sempre começar criptografia tão logo a compressão tenha terminado. Por que o nível de criptografia é processado em tamanhos variáveis, dois ou mais agrupamentos de dados de nível de compressão podem ter de ser comprimidos antes que um agrupamento de dados do nível de criptografia possa começar a criptografia. Assim sendo, é necessário para a estrutura em árvore 313 determinar essas dependências de dados 304 para otimizar o processamento de uma determinada solicitação de I/O 403. Mais ainda, quando a solicitação de I/O requer recuperação de dados dos múltiplos dispositivos de armazenamento/de mídia, conforme as dependências de dados 304 delineadas na estrutura em árvore 313 pode permitir simultâneos processamentos de dados a partir dos diferentes dispositivos de armazenamento/de mídia, mais propriamente do que tendo dados de um dispositivo de mídia/de armazenamento processados enquanto o outro

Petição 870190110896, de 30/10/2019, pág. 28/92 / 39 dispositivo de mídia/de armazenamento fica ocioso.

[0049] O produto final associado com a estrutura em árvore 313 é um mapa definindo uma ordem ótima de processamento para uma determinada solicitação de I/O 403. Independente da otimização da programação de solicitações de I/O, cada solicitação de I/O 403 é individualmente otimizado pela estrutura em árvore 313 tal que ela pode ser completada na menor quantidade de tempo possível. Esta solicitação de I/O 403 e sua estrutura em árvore associada 313 são então alimentadas para o programador 303 para eficiente programação.

[0050] É importante notar que os dados associados com uma solicitação de I/O pode ter muito mais camadas de processamento do que as descritas acima. A estrutura em árvore não eficazmente atende a solicitação de I/O, mas somente cria um mapa de como a solicitação de I/O individual pode ser atendida de modo mais ótimo.

[0051] Por meio de exemplo, e não por meio de limitação, uma solicitação de I/O pode ser quebrada em uma estrutura em árvore na qual cada agrupamento de dados de dados em cada camada em processar a solicitação é tratada por uma correspondente instrução. Uma dada instrução dentro de uma camada da estrutura em árvore pode ter dependências de dados associadas indicando uma ou mais instruções de uma camada anterior que precisa ser completada Antes que a dada instrução poder iniciar a execução.

[0052] Tabela V fornece um exemplo de uma estrutura em árvore para uma solicitação de I/O. Na tabela I, cada instrução usa dados identificados por um nome de caminho, desvio e comprimento em kilobytes (KiB). Neste exemplo, a ordem de processamento das camadas dentro da estrutura em árvore é de baixo para cima. Contudo, as instruções dentro da estrutura em árvore podem ser executadas em paralelo na medida em que as dependências de dados são satisfeitas. Na tabela V, a dependência para uma dada instrução indica que outra instrução(s) precisa ser completada a partir da camada abaixo Antes que a dada instrução poder começara a execução. Neste

Petição 870190110896, de 30/10/2019, pág. 29/92 / 39 exemplo, nomes de caminho começando com com/dev_ se refere aos dispositivos de mídia. Especificamente,/dev_hdd0 e/dev_hdd1 se referem aos mecanismos de disco rígido e/dev_bdvd0 se refere a um mecanismo de vídeo digital de alta definição (DVD). Nomes de caminho não começando com com/dev_ se referem aos arquivos virtuais que são compostos de dados recuperados por outras instruções.

TABELA V

Instrução #	(nome, desvio, comprimento (KiB))	dependência
0	(/userfile.dat, 0, 1200)	1, 2, 3, 4
Camada de agrupamento de dados executora de Patch
1	(/userfile.dat, 0, 400)	5-11
2	(/xxx.pspatch, 1, 1)	12
3	(/userfile.dat, 800, 400)	13-19
4	(/xxx.pspatch, 2, 399)	12, 20-25

Camada de agrupamento de dados desaquivadora

5	(/userfile.dat, 0, 64)	26
6	(/userfile.dat, 64, 64)	27
7	(/userfile.dat, 128, 64)	28
8	(/userfile.dat, 192, 64)	29
9	(/userfile.dat, 256, 64)	30
10	(/userfile.dat, 320, 64)	31
11	(/userfile.dat, 384, 64)	32
12	(/xxx.pspatch.dat, 0, 64)	33
13	(/userfile.dat, 768, 64)	34
14	(/userfile.dat, 384, 64)	35
15	(/userfile.dat, 384, 64)	36
16	(/userfile.dat, 384, 64)	37
17	(/userfile.dat, 384, 64)	38
18	(/userfile.dat, 384, 64)	39
19	(/userfile.dat, 384, 64)	40
20	(/xxx.pspatch.dat, 64, 64)	41
21	(/xxx.pspatch.dat, 128, 64)	42
22	(/xxx.pspatch.dat, 192, 64)	43
23	(/xxx.pspatch.dat, 256, 64)	44
24	(/xxx.pspatch.dat, 320, 64)	45
25	(/xxx.pspatch.dat, 384, 64)	46

Camada de Transformada desaquivadora (descompressão)

26	(game.psarc, 500, 27)	47-48
27	(game.psarc, 527, 35)	48
28	(game.psarc, 562, 31)	48
29	(game.psarc, 593, 17)	48
30	(game.psarc, 610, 50)	48-49
31	(game.psarc, 660, 38)	49
32	(game.psarc, 698, 34)	49
33	(patch.psarc, 100, 19)	50
34	(game.psarc, 1132, 18)	51
35	(game.psarc, 1150, 18)	51-52
36	(game.psarc, 1182, 29)	52
37	(game.psarc, 1211, 29)	52
38	(game.psarc, 1240, 64) - descomprimida	52-53
39	(game.psarc, 1304, 40)	53
40	(game.psarc, 1442, 39)	53
41	(patch.psarc, 119, 64) - descomprimida	50, 54
42	(patch.psarc, 183, 50)	54

Petição 870190110896, de 30/10/2019, pág. 30/92 / 39

43	(patch.psarc, 233, 17)	54
44	(patch.psarc, 250, 26)		54-55
45	(patch.psarc, 276, 35)		55
46	(patch.psarc, 311, 15)		55
Camada de Cache Ram (blocos de 128 KiB)
47	(game.psarc, 384, 128)		56
48	(game.psarc, 512, 128)		57
49	(game.psarc, 640, 128)		58
50	(patch.psarc, 0, 128)		59
51	(game.psarc, 1024, 128)		60
52	(game.psarc, 1152, 128)		61
53	(game.psarc, 1280, 128)		62
54	(patch.psarc, 128, 128)		63
55	(patch.psarc, 256, 128)		64
Camada de Descriptografia (blocos de 128 KiB)
56	(game.psarc, 384, 128)		65
57	(game.psarc, 512, 128)		66
58	(game.psarc, 640, 128)		67
59	(patch.psarc, 0, 128)		68
60	(game.psarc, 1024, 128)		69
61	(game.psarc, 1152, 128)		70
62	(game.psarc, 1280, 128)		71
63	(patch.psarc, 128, 128)		72
64	(patch.psarc, 256, 128)		73
Camada de Sobreposição(translação de trajeto)
65	(/dev_bdvd/game.psarc, 384, 128)		74
66	(/dev_bdvd/game.psarc, 512, 128)		75
67	(/dev_bdvd/game.psarc, 640, 128)		76
68	(/dev_hdd/game.psarc, 0, 128)		77
69	(/dev_bdvd/game.psarc, 1024, 128)		79
70	(/dev_bdvd/game.psarc, 1152, 128)		81
71	(/dev_bdvd/game.psarc, 1280, 128)		83
72	(/dev_hdd/game.psarc, 128, 128)		96
73	(/dev_hdd/game.psarc, 256, 128)		97
Camada de Cache HDD (Decide hit/fill/readthru)
74	(Zdev_hdd1Zcache.dat, 16384, 128) hit
75	(Zdev_hdd1Zcache.dat, 16512, 128) hit
76	(/dev_hdd1/cache.dat, 16640, 128) hit
77	(/dev_hdd0/patch.psarc, 0, 128) RT
78	(/dev_hdd1/cache.dat, 17024, 128) write fill		94, 79
79	(/dev_bdvd/game.psarc, 1024, 128) read fill
80	(/dev_hdd1/cache.dat, 17152, 128) write fill		94, 81
81	(/dev_bdvd/game.psarc, 1152, 128) read fill
82	(/dev_hdd1/cache.dat, 17280, 128) write fill		94, 83
83	(/dev_bdvd/game.psarc, 1280, 128) read fill
84	(/dev_hdd1/cache.dat, 17408, 128) write fill		94, 85
85	(/dev_bdvd/game.psarc, 1408, 128) read fill
86	(/dev_hdd1/cache.dat, 17536, 128) write fill		94, 87
87	(/dev_bdvd/game.psarc, 1536, 128) read fill
88	(/dev_hdd1/cache.dat, 17664, 128) write fill		94, 89
89	(/dev_bdvd/game.psarc, 1664, 128) read fill
90	(/dev_hdd1/cache.dat, 17792, 128) write fill		94, 91
91	(/dev_bdvd/game.psarc, 1792, 128) read fill
92	(/dev_hdd1/cache.dat, 17920, 128) write fill		94, 93
93	(/dev_bdvd/game.psarc, 1920, 128) read fill
94	(Zdev_hdd1Zcache.idxm 32, 1) atualizar	escrita
	// encrita inicial de bloco de marcação de índice ocupado//
95	(Zdev_hdd0Zpatch.psarc, 128, 128) atualizar	escrita	80, 82, 84, 86,
	// escrita final de controles de VRW de bloco de marcação de	88, 90, 92, 94
	índice//
96	(/dev_hdd0/patch.psarc, 128, 128) RT
97	(/dev_hdd0/patch.psarc, 256, 128) RT

Petição 870190110896, de 30/10/2019, pág. 31/92 / 39 [0053] No exemplo apresentado na tabela V, a solicitação de I/O é para um arquivo digital DVD. As camadas individuais dentre da estrutura em árvore neste exemplo, são executadas em uma ordem de “baixo para cima”. Por isso se entende que pelo menos, algumas das instruções na camada mais baixa precisam ser executadas inicialmente devido às dependências de dados. Como usado aqui, o termo “camada mais baixa” se refere àquela camada da estrutura para a qual não há camada anterior (ou mais baixa). Por nenhuma camada anterior (ou mais baixa), se entende que nenhuma das instruções na camada mais baixa tem uma dependência de dados requerendo término anterior da execução de uma instrução em uma camada diferente. Contudo, é possível que um ou mais instruções na camada mais inferior possam ter dependências de dados que requerem término anterior da execução de outras instruções na camada mais inferior. No exemplo descrito com relação à tabela I acima, a camada mais baixa é a camada de cache de HDD. A ordem exata de atendimento das instruções na tabela V pode depender, até certo ponto nas dependências de dados dentro das instruções na camada de cache de HDD. Por meio de exemplo, as solicitações de I/O finais na camada de cache de HDD da tabela V pode ser classificada pelo dispositivo/partição na ordem de execução mostrada na tabela VI abaixo.

TABELA VI

Instrução #	(nome, desvio, comprimento (KiB))	dependência
94	(/dev hdd1/cache.idxm 32, 1) write
74	(/dev hdd1/cache.dat, 16384, 128) read
75	(/dev hdd1/cache.dat, 16512, 128) read
76	(/dev hdd1/cache.dat, 16640, 128) read
78	(/dev hdd1/cache.dat, 17024, 128) write *	94, 79
80	(/dev hdd1/cache.dat, 17152, 128) write *	94, 81
82	(/dev hdd1/cache.dat, 17280, 128) write *	94, 83
84	(/dev hdd1/cache.dat, 17408, 128) write *	94, 85
86	(/dev hdd1/cache.dat, 17536, 128) write *	94, 87
88	(/dev hdd1/cache.dat, 17664, 128) write *	94, 89
90	(/dev hdd1/cache.dat, 17792, 128) write *	94, 91
92	(/dev hdd1/cache.dat, 17920, 128) write *	94, 93
95	(/dev_hdd0/patch.psarc, 128, 128) write *	78, 80, 82, 84, 86, 88, 90, 92
77	(/dev hdd0/patch.psarc, 0, 128) read
96	(/dev hdd0/patch.psarc, 128, 128) read
97	(/dev hdd0/patch.psarc, 256, 128) read
79	(/dev bdvd/game.psarc, 1024, 128) read

Petição 870190110896, de 30/10/2019, pág. 32/92 / 39

81	(/dev bdvd/game.psarc, 1152, 128) read
83	(/dev bdvd/game.psarc, 1280, 128) read
85	(/dev bdvd/game.psarc, 1408, 128) read
87	(/dev bdvd/game.psarc, 1536, 128) read
89	(/dev bdvd/game.psarc, 1664, 128) read
91	(/dev bdvd/game.psarc, 1792, 128) read
93	(/dev bdvd/game.psarc, 1920, 128) read

[0054] As instruções na tabela VI poderiam todas serem emitidas em paralelo, com a exceção daqueles com dependências marcadas (*), que pode ser classificado e expedido pelo programador 303. Especificamente, porque instrução de escrita de índice 94 e instruções de leitura 77, 79, 81, 83, 85, 87, 89, 91, e 93 não têm qualquer dependências de dados dessas instruções, pode ser executadas em paralelo e em qualquer ordem. Instruções de escrita 78, 80, 82, 84, 86, 88, 90, e 92 dependem da instrução de escrita de índice 94 e instruções de leitura 77, 79, 81, 83, 85, 87, 89, 91, e 93 iniciais respectivamente. Conseqüentemente cada uma dessas instruções de escrita precisam esperar até escrita de índice 94 e a correspondente instrução de leitura ter sido executada.

[0055] As instruções remanescentes na estrutura em árvore descritas pela tabela I acima podem ser executadas em paralelo na medida em que as dependências de dados são satisfeitas. É importante notar que incluindo as dependências de dados na estrutura em árvore criada imediatamente após receber uma solicitação de I/O cada instrução em uma determinada camada da estrutura em árvore pode ser executada tão logo os requisitos de dependências de dados para aquela instrução tenha sido encontrado. Conseqüentemente, é possível executar instruções para duas diferentes camadas em paralelo enquanto as dependências de dados para cada instrução tenham sido encontradas. Assim sendo, uma instrução em uma camada não necessita esperar pelo término de todas as instruções na camada anterior.

[0056] Por exemplo, de modo a executar instrução 0 de solicitação de I/O, instruções do executor de patch 1, 2, 3, 4 precisam primeiro ser completadas. Antes que a instrução do executor de patch 4 possa ser executada, somente instruções de desarquivamento 12 e 20-25 precisam ser

Petição 870190110896, de 30/10/2019, pág. 33/92 / 39 completadas. Antes que a instrução de desarquivamento 25 possa ser executada, instrução de descompressão 46 somente precisa ser completada. Antes que a instrução de descompressão 46 possa começar, somente instrução de cache de ram 55 precisa ser completada. Antes que a instrução de cache de ram 55 possa começar somente instrução de descriptografia 64 precisa ser completada. Antes que a instrução de descriptografia 64 possa começar, somente instrução de overlay 73 precisa ser completada. Antes que a instrução de overlay 73 possa começar somente instrução de cache de HDD 97 precisa ser completada.

[0057] Uma vez que a solicitação de I/O 403 passou através da camada de estrutura em árvore 301, e uma ordem de processamento para aquela particular solicitação de I/O é determinada, a solicitação de I/O 403 é movida para uma fila entrante 404 pelo programador 303. Por meio de exemplo, a fila entrante 404 pode ser uma fila primeiro a entrar é o primeiro a sair (FIFO) fila onde a primeira solicitação colocada na fila 404 é a primeira solicitação programada pelo programador 303. Inserção da solicitação 403 na fila entrante 404 pode ser implementada por uma operação atômica para prevenir threads de serem bloqueados quando solicitando I/O assíncronos. Em algumas modalidades, a fila entrante 404 pode ser na forma de uma pilha atômica, que pode ser preenchida pelo processador auxiliar 105B com uma troca atômica.

[0058] Por meio de exemplo, e não por meio de limitação, se a solicitação de I/O 403 é uma operação de leitura, a aplicação cliente 401 pode fornecer uma área de armazenamento temporário 405 para receber dados recuperados de um dispositivo de mídia. Quando a solicitação de I/O 403 é completada, a aplicação cliente 401 pode ler os dados recuperados a partir da área de armazenamento temporário 405 que ele forneceu. Quando o cliente terminou de processar a solicitação de I/O 403, o cliente pode desalocar a área de armazenamento temporário 405 tal que seus recursos estão disponíveis

Petição 870190110896, de 30/10/2019, pág. 34/92 / 39 para uso I/O futuro.

[0059] A solicitação de I/O 403 pode ativar o programador 303 se o programador 303 não está já ativada. A aplicação 401 pode então esperar pela solicitação de I/O 403 a ser completada. Por exemplo, a aplicação cliente 401 pode indagar periodicamente usando um método atômico (e.g., isDone()). Alternativamente, o cliente pode esperar por uma função de chamada de volta 411 que o programa de FIOS 101 chama quando a solicitação de I/O 403 é completada.

[0060] Após a solicitação de I/O 403 ter sido inserido na fila entrante 404, o programa de FIOS 101 pode invocar o programador 303 para efetuar uma inserção de programação 407. A seqüência de operações implementada pelo programador 303 pode ser entendido com referência à FIG. 5. O programador 303 pode adormecer (i.e., permanecer inativo) como indicado em 502 se não há I/O a tratar. Quando uma nova solicitação de I/O 403 entra uma fila entrante 404, o programador 303 acorda para tratá-la. Uma vez que o programador 303 acorda (ou já está acordado), ele nota a nova solicitação 403 na fila entrante 404 e ele move a solicitação em uma localização apropriada na fila de programação 406.

[0061] Para determinar a posição na fila da solicitação de I/O 403, o programador 303 pode opcionalmente determinar um estado corrente do dispositivo de mídia e.g., indagando a camada de dispositivo de mídia 307 ou uma outra camada na pilha de mídia do FIOS 300 como indicado em 503. Os dados de estado podem variar dependendo do tipo de dispositivo de mídia tratado pela pilha de mídia do FIOS 300 e nas várias camadas presente na pilha 300. Exemplos incluem, endereço de bloco lógico mais recentemente acessado (LBA), o desvio e último caminho acessado da RAM cachê, a camada de disco corrente, a posição da cabeça, modo de seqüenciamento, e modo de não seqüenciamento.

[0062] De acordo com modalidades da presente invenção, o

Petição 870190110896, de 30/10/2019, pág. 35/92 / 39 programador 303 pode ser baseado no modelo de desempenho do dispositivo de mídia 303A. Ao contrário dos existentes, programadores de I/O, o modelo de mecanismo 303A pode levar em conta dados considerando o desempenho do dispositivo de mídia 118 em determinar uma programação ótima da solicitação 403. Programação de solicitações de I/O 403 usando um modelo de mecanismo pode ser comparado ao inverso do processo de gravação de áudio ao gerar um CD. O modelo de desempenho 303A pode ser configurado para levar em conta tais fatores como overhead, tempo de movimento do disco, tempo de leitura, e o similar. O modelo de desempenho 303A pode modelar de forma arbitrária, características complexas do dispositivo de mídia 118, tal como capacidade de retransmissão, laser wiggles, movimentos da cabeça de leitura, mudanças de camada, e excesso de solicitações. O modelo de desempenho 303A pode também levar em conta outros parâmetros do particular meio sendo lido ou escrito pelo dispositivo de mídia 118 envolvido na solicitação de I/O. Por exemplo, o modelo de desempenho 303A pode considerar se o dispositivo está lendo de um disco de camada única ou disco de múltiplas camadas, e.g., discos de camada dual, tal como um DMD de BluRay.

[0063] O programador 303 pode também opcionalmente olhar os requisitos de tempo de solicitação de I/O (e.g., prazos) e prioridade como indicado na 504. O programador pode também opcionalmente ser configurado para comparar solicitações de I/O na fila entrante 404 com solicitações de I/O na fila de programação 406 para intercalar como indicado em 506. As dependências de dados 304 delineado por uma estrutura em árvore 313 de uma determinada solicitação de I/O na fila entrante 404 pode ter sobreposição com as dependências de dados 304 delineadas pelas estruturas em árvore 313 de uma ou mais solicitações de I/O já na fila de programação 406. Por exemplo, uma solicitação de I/O na fila entrante 404 pode necessitar ler um agrupamento de dados de dados a partir de um determinado dispositivo de

Petição 870190110896, de 30/10/2019, pág. 36/92 / 39 mídia e uma solicitação de I/O em uma fila de programação 406 pode necessitar ler um agrupamento de dados vizinho de dados do mesmo dispositivo de mídia. Assim sendo intercalando essas duas solicitações de I/O, a eficiência de processar aquelas solicitações de I/O pode ser melhorada. A intercalação pode ser feita estabelecendo um valor de sobreposição limite entre duas determinadas estruturas em árvore 313 e intercalar as duas solicitações de I/O associadas com aquelas estruturas em árvore 313 quando o valor de sobreposição limite é encontrado. Se duas ou mais solicitações de I/O são intercaladas, então o programador pode tratar essas solicitações intercaladas como uma única solicitação durante a programação.

[0064] Uma vez que é determinado se quaisquer solicitações de I/O podem ser intercaladas, o programador 303 pode determinar a melhor localização da fila para a presente solicitação de I/O como indicado em 507. O programador 303 pode começar colocando a solicitação de I/O entrante em uma posição arbitrária da fila de programação. O tempo total necessita completar a inteira programação, assim como considerações de prioridade, e restrições de prazo são então determinadas usando esta fila de programação de verificação. Este processo pode ser repetido iterativamente com ordens de fila diferente até uma melhor ordem de fila de programação ser determinada, como indicado em 507. Note que o estado inicial para a solicitação 403 pode ser determinado a partir do estado final para a solicitação anterior na ordem da programação e o estado inicial para a próxima solicitação na ordem de programação pode ser determinado a partir do estado final da solicitação 403.

[0065] O programador 303 pode caminhar através das solicitações na fila de programação, comparando as características da solicitação 403 contra aquelas solicitações que já estão na fila. O programador 303 pode tentar a solicitação 403 em cada possível localização na fila, procurando por substituição de prioridade, prazos perdidos, e considerações de tempo. O programador 303 pode determinar um melhor possível nova ordem de fila

Petição 870190110896, de 30/10/2019, pág. 37/92 / 39 procurando uma ordem na qual nenhuma operação de I/O solicitado perde seu prazo. Se uma ou mais solicitações precisam perder seus prazos, o programador pode determinar uma ordem de fila usando diferentes critérios. Critérios adicionais que podem afetar a ordenação das solicitações na fila de programação 406 podem incluir (mas não são limitados à) prioridades de solicitação de I/O, área de armazenamento temporário de fluxo de estados, requisitos de latência, e dependências de sobreposição de dados entre estrutura em árvores de diferentes solicitações de I/O.

[0066] Em algumas modalidades, prioridades podem ser usadas, e.g., se todos os prazos não podem ser resolvidos. Por exemplo, se alguns prazos de modo inevitável serão perdidos, a melhor ordem da fila pode ser uma na qual solicitações de prioridade possivelmente mais baixa perdem seus prazos. Se há múltiplas possíveis ordens de fila que vão de encontro com a consideração anterior, então a ordem de fila que tem o número mais baixo de solicitações de igual prioridade perdendo prazos pode ser a melhor ordem. Se há múltiplas possíveis ordens de fila nas quais todas as considerações anteriormente descritas são iguais, então uma ordem de fila com o tempo mais baixo possível para executar a fila completa pode ser a melhor ordem. Em alguns casos, uma solicitação de prioridade baixa pode ser programada antes de uma solicitação de prioridade alta enquanto a solicitação de prioridade alta pode cumprir seu prazo.

[0067] Se há múltiplas ordens de fila possíveis nas quais todas as considerações anteriormente descritas são iguais, então a ordem onde as solicitações mais novas na fila de programação 406 vai para o fim da fila pode ser a melhor ordem.

[0068] Uma vez que o programador 303 determinou a melhor na fila de programação 406 para cumprimento da solicitação 403, a solicitação pode ser inserida nela, como indicado em 407 na FIG. 4, e 508 na FIG. 5. Referindo de novo à FIG. 4, se há recursos disponíveis para executar as

Petição 870190110896, de 30/10/2019, pág. 38/92 / 39 solicitações de I/O, o programador 303 pode mover a primeira solicitação na fila de programação 406 para uma fila de emissão 408 como indicado em 409. A solicitação pode então ser executada a partir da fila de emissão 408. Para executar uma determinada solicitação de I/O 403, o programador 303 pode passar a solicitação 403 assim como a estrutura em árvore 313 associada com a determinada solicitação 403 para as primeiras camadas na pilha de mídia do FIOS 300.

[0069] Cada camada abaixo o programador 303 pode ver solicitação de I/O 403 e correspondente estrutura em árvore passada para ele pela camada acima. Se apropriado, a camada pode processar os agrupamentos de dados 304 de dados associados com uma solicitação. Cada camada processa a solicitação 403 de acordo com a estrutura em árvore 313 associada com a solicitação 403, tal que a solicitação é processada na maneira mais eficiente possível. Por meio de exemplo, e não por meio de limitação, se a solicitação é uma operação de leitura, a camada de desarquivamento 308 pode verificar o nome do caminho fornecido contra o conteúdo de arquivos abertos, e, se ela acha o arquivo, pode re-mapear a solicitação em uma leitura dos dados comprimidos, Cada camada da pilha de mídia do FIOS 300 passa a solicitação de I/O processada ou não processada para a próxima camada inferior até que a solicitação finalmente alcança a camada de hardware 310. Quando a camada de hardware 310 responde à solicitação, a resposta vai através de cada camada na pilha de mídia 300, de baixo para cima, e cada camada pode processar o agrupamentos de dados 302 de dados recuperados se apropriado. Por exemplo, a camada de descompressão pode saber que o agrupamento de dados 302 de dados retornados precisam ser descomprimidos, assim ele o descomprime antes de passar a resposta de volta para a pilha 300. A resposta finalmente vai de volta para o programador 303.

[0070] Quando dados recuperados voltam para cima da pilha 300, o programador 303 pode recebê-los e então move a solicitação de I/O 403 para

Petição 870190110896, de 30/10/2019, pág. 39/92 / 39 uma fila de completados 410, que pode acionar uma função de chamada de volta 411 para uma aplicação 401 (se a chamada de volta foi estabelecida pela aplicação). Alternativamente, a aplicação 401 pode pesquisar a pilha do FIOS 300 para determinar se uma solicitação de I/O 403 foi completada. Uma vez que uma solicitação de I/O 403 foi completada, ela pode ser movida para um conjunto de I/O livre 412. O conjunto de I/O livre 412 pode conter um conjunto de solicitações de I/O que não estão em uso. Tais solicitações podem incluir aquelas que nunca foram alocadas para uma aplicação cliente 401 ou aquelas que foram usadas por uma aplicação cliente 401 e então liberadas para uso de novo. Quando a aplicação cliente 401 faz uma solicitação de I/O 403, o programador 303 pode alocar uma solicitação de I/O ao cliente aplicação deste conjunto 412. O conjunto de I/O livre 412 pode ser implementado como uma pilha. Solicitações de I/O livre podem ser pegos a partir do conjunto de I/O livre 412 e colocados em uma fila entrante 404. Nesta maneira, as solicitações de I/O livres podem ser reutilizadas.

[0071] De acordo com modalidades da invenção, o programador 303 pode operar em um enlace de programação como a seguir:

1. Verificar por término de I/O

2. Emitir novas solicitações de I/O

3. Emitir chamadas de volta de I/O (se alguma)

4. Inserção para programação (programar inserção de entrante)

5. Novas emissões de novo.

6. Verificar por prazos perdido prognosticados.

7. Retornar a 1.

[0072] O número de inserções programadas para cada iteração pode ser limitada para algum número máximo, e.g., dezesseis inserções.

[0073] Em algumas modalidades da invenção, uma unidade de processador auxiliar 105B (e.g., SPE 206) poderia solicitar I/O para si própria adicionando uma solicitação de I/O entrante para uma fila entrante 404

Petição 870190110896, de 30/10/2019, pág. 40/92 / 39 através de uma troca que é atômica com relação ao processador principal 105A ou PPE 204. Por exemplo, em uma implementação de processador célula convencional, um SPE 206 poderia não ter quaisquer facilidades de I/O. Contudo, se a fila entrante 404 é um elemento de dados comum, um processador auxiliar 105B poderia adicionar uma solicitação de I/O para a fila através de uma mudança atômica padrão com o processador principal 105A e sinalizar o processador principal 105A.

[0074] Em muitas implementações da técnica anterior, se um processador auxiliar 105B necessita dados para processamento imediato, aqueles dados têm de estar na memória principal. Ao contrário, com modalidades da presente invenção, o processador auxiliar 105B pode acionar a pilha de mídia do FIOS 300 para ir pegar os dados necessários do dispositivo de mídia 118 rígido ou mesmo da network 127.

[0075] Por meio de exemplo, e não por meio de limitação, a fila entrante 404, fila de completados 410 e o conjunto de I/O livre 412 podem se pilhas atômicas. O processador auxiliar 105B pode pegar uma solicitação de I/O do conjunto de I/O livre 412, preencher um caminho para a solicitação de I/O, colocar a solicitação de volta na fila entrante 404 e então efetuar sincronização e acordar o programador 302. O processador auxiliar 105B pode fazer outro trabalho enquanto intermitentemente indagando pelo término da solicitação de I/O.

[0076] Por meio de exemplo, no sistema de processador célula 200, uma solicitação de I/O pode ser atendido por um SPE 206. Os dados solicitados pelo SPE 206 podem ser enviado para qualquer lugar endereçável pelo PPE 204. Se o SPE 206 foi bloqueado, a pilha de mídia do FIOS 300 poderia escrever os dados diretamente para o depósito local (LS) do SPE 206. Em algumas modalidades, um SPE 206 pode solicitar a camada de descompressão para fazer descompressão com um outro SPE. Isto pode ser implementado, e.g., usando uma chamada de procedimento remoto (RPC)

Petição 870190110896, de 30/10/2019, pág. 41/92 / 39 entre processadores. Neste exemplo, um SPE 206 solicita ao PPE 204 para fazer alguma coisa para ele. Em uma RPC mais convencional, isto é o contrário.

[0077] Em algumas modalidades, a camada de cache programador 312 (e.g. um cache de HDD) pode ser usado para pré-buscar um arquivo do dispositivo de mídia 118 no cache 117 no dispositivo de armazenamento 115 tal que o arquivo pode ser lido rapidamente mais tarde. Em tal um caso, uma operação de pré-busca 413 pode ser inserida diretamente na fila de emissão 408. A pré-busca pode ser uma pré-busca manual padrão que foi implementado por muitos tipos de caches, tal como a instrução “dcbt” na arquitetura de CPU do PowerPC. De acordo com modalidades da invenção, as pré-buscas podem ser enfileiradas e executadas como parte do enlace do programador descrito acima. Pré-busca pode facilitar o trabalho com mídia de fonte relativamente lenta (e.g., Blu-Ray e UMD), com latência relativamente alta, e baixa capacidade de retransmissão que precisa ser acessada enquanto outras solicitações de I/O estão sendo realizadas.

[0078] O programador 302 pode ser configurado para implementar tal pré-busca em um prioridade relativamente baixa tal que ele vai somente executar nos momentos não usados quando o dispositivo de mídia 118 por outro lado estaria ocioso, e não vai interferi com outras solicitações de I/O. Por exemplo, o sistema 100 pode ter um dispositivo de mídia lento 118 (e.g., um disco óptico tal como um mecanismo de disco de Blu-Ray (BD)) e um dispositivo de armazenamento mais rápido 115, tal como um mecanismo de disco rígido. A camada de cache programador 305 pode ser usado para de modo assíncrono copiar um arquivo a partir do mecanismo de disco óptico para o disco rígido. Quando o arquivo é acessado mais tarde será lido na maior velocidade do HDD (e.g., 20MiB/s) em vez da velocidade de disco óptico mais lento (e.g., 8 MiB/s).

[0079] Embora cache de pré-busca seja normalmente feita para um

Petição 870190110896, de 30/10/2019, pág. 42/92 / 39 cachê de disco rígido, a pré-busca também pode ser feito para a memória principal 106, 202. Solicitações de pré-busca podem ser incluídas no fim da fila de programação 406 na ordem na qual elas são recebidas após programação ser completada. Em algumas modalidades, solicitações de prébusca podem ser atrasadas quando necessário. Solicitações de pré-busca não são programadas na mesma maneira que outras solicitações de I/O 403. Solicitações de pré-busca são mantidas em uma separada fila de pré- busca 413 que é somente atendida quando a fila de programação 406 está vazia. Uma solicitação de pré-busca pode ser atrasada, se necessária. Por outro lado, pré-buscas podem ser completadas na ordem na qual elas são recebida. O programador 303 pode manter as solicitações de pré-busca enfileirada e somente executá-las quando o subsistema de I/O ficar ocioso por um comprimento de tempo especificado. Isto previne solicitações de pré-busca de interferir com solicitações de I/O normais. Em adição, pré-buscas são também não limitadas a um único bloco de cache, eles podem ser de qualquer tamanho, ou mesmo passar um valor “arquivo como um todo” especial que diz ao cache para carregar um arquivo inteiro do começo ao fim. Ainda mais, embora pré-buscas possam ser de qualquer tamanho, as pré- busca s podem ser implementados tal que não mais do que um bloco de cache é preenchido antes de retornar ao programador 303 para verificar que a pilha de mídia do FIOS 300 continua a estar ociosa [0080] Pré-busca de cache pode fornecer desempenho de I/O melhorado em aplicações orientadas por operação de I/O, tal como jogos de vídeo e em plataformas com necessidades de I/O específicas, tal como consoles de jogo de vídeo moderno. Em particular, os dados de jogo é freqüentemente armazenada em uma mídia lenta tal como uma mídia óptica ou servidor de arquivo de rede, mas o jogo pode ter acesso à depósito local rápido como HDD.

[0081] Modalidades da presente invenção fornece desempenho de I/O

Petição 870190110896, de 30/10/2019, pág. 43/92 / 39 melhorado em aplicações e sistemas que utilizam uma significativa quantidade de I/O. Como discutido acima, modalidades da presente invenção são particularmente úteis em aplicações de jogo de vídeo e sistemas de jogo de vídeo. Contudo, as modalidades da invenção não são limitadas a tais aplicações e sistemas.

[0082] Outras variações nas modalidades descritas acima estão dentro do escopo das modalidades da presente invenção. Por exemplo, em algumas implementações, patch de arquivos pela camada de executor de patch 322 pode ser implementada através do uso de patches de diferença binários (diff de binário) que são aplicados em tempo de execução. Por meio de exemplo, patches de diff de binário 119 podem ser armazenados no dispositivo de armazenamento 115 e aplicados aos arquivos relevantes em tempo de execução.

[0083] Tradicionalmente patches foram aplicados criando um arquivo totalmente novo seguindo instruções executáveis a partir de um arquivo de diferença que poderia ser baixado sobre uma rede. Essas instruções poderiam indicar quais bytes são para serem removidos a partir de um arquivo e quais bytes são para serem adicionados ao arquivo. Os patches de diff de binário 119 armazenado no dispositivo de armazenamento 115 pode incluir tais instruções. Patch tradicionalmente tem sido feito off-line, i.e., não em tempo de execução. Em um patch tradicional típico, um inteiro arquivo original é lido na memória a partir de um dispositivo de armazenamento. Patches de diferença são aplicados ao arquivo para gerar um novo arquivo, que é então escrito de volta ao dispositivo de armazenamento. A idéia é minimizar o tamanho do patch a baixar.

[0084] Patches de diff foram desenvolvidos em um tempo quando baixa foi realizada por modems de 300 baud ou 1200 baud. Naquele tempo era importante reduzir o tamanho da baixa. Com o desenvolvimento da Internet, velocidades de baixa maiores têm se tornado mais amplamente

Petição 870190110896, de 30/10/2019, pág. 44/92 / 39 disponíveis. É uma mais comum prática, por conseguinte, ajustar a transferência de um inteiro arquivo sobre a rede e o baixa para o dispositivo de armazenamento 115 sem usar patch de diff. Esta abordagem, embora um pouco rude é, todavia, eficaz.

[0085] Contudo, em muitas aplicações, particularmente jogos de vídeo, é freqüentemente necessário aplicar patch de arquivos muito grande. Já que um inteiro arquivo precisa ser carregado na memória de modo a aplicar uma patch, patch de diff pode potencialmente ser lento para arquivos muito grande. Por exemplo, ler um arquivo de 1 Gig a partir de um depósito na memória pode tomar mais do que um minuto mesmo antes de aplicar o patch. [0086] Ambas técnicas anteriores que abordam patch podem apresentar um problema devido aos custos de largura de banda. O problema é particularmente agudo onde um arquivo de substituição a ser baixado ocupa uma porção significativo do espaço disponível no dispositivo de armazenamento 115. Por exemplo, baixar um arquivo corrigido por patch de 500 Megabyte pode tomar uma porção significativa de um disco rígido de 20 Gigabyte.

[0087] Ainda mais, situações podem surgir onde vários arquivos muito grande requerem substituição de uma quantidade muito pequena de dados. Por exemplo, uma aplicação pode ter vários arquivos com um problema em um ID de 16 byte no começo de cada arquivo. Contudo, porque o patch somente trabalha a nível de tamanho de arquivo, aplicando o patch por arquivo substituição vai significar baixar e substituir cada arquivo único na aplicação. Isto é não realístico se a quantidade de arquivos é de vários gigabytes de data. Mesmo se os arquivos foram corrigidos por patch com uma tradicional patch de diff, todos os arquivos teriam de ser copiados de modo a aplicar o patch.

[0088] Para superar esses problemas um patch de diff de binário pode ser gerado e baixado na maneira tradicional. Contudo, em vez de aplicar o

Petição 870190110896, de 30/10/2019, pág. 45/92 / 39 patch off-line, o patch pode ser aplicado em tempo de execução, e.g., como parte de atender uma solicitação de I/O a partir de uma aplicação enquanto a aplicação está executando, É notado que compor agrupamento de dados imediato conforme descrito acima, embora vantajoso, não é requerido de modo a implementar tais patches de diff de binário em tempo de execução.

[0089] Patches podem ser aplicadas em um estágio relativamente cedo na estrutura em árvore. Por exemplo, parte do processamento inicial de uma solicitação de I/O entrante pode envolve verificar uma tabela de patch para determinar se há um patch de diff para quaisquer arquivos listados na solicitação. Isto é similar à procura de TOC desarquivador descritos acima. A tabela de patch, que pode ser armazenada na RAM, contém informação necessária pelo FIOS 101 de modo a determinar como e onde aplicar os patches.

[0090] Enquanto a discussão acima é uma descrição completa da modalidade preferida da presente invenção, é possível usar várias alternativas, modificações e equivalentes. Por conseguinte, o escopo da presente invenção deve ser determinado não com referência a descrição acima mas deve, em seu lugar, ser determinado com referência às reivindicações anexas, junto com seu total escopo de equivalentes. Qualquer recurso, se preferido ou não, pode ser combinado com qualquer outro recurso, se preferido ou não. Nas reivindicações que seguem, o artigo indefinido “um”, ou “uma” se refere a uma quantidade de um ou mais do item seguindo o artigo, exceto onde expressamente colocado ao contrário. Qualquer elemento em uma reivindicação que de forma explícita não coloca “significa por” efetuando uma função especificada, não é para ser interpretado como um cláusula “meio” ou “etapa” como especificado no 35 USC § 112, ⁽|| 6. Em particular, o uso de “etapa de” nas reivindicações não é pretendida para invocar as disposições de 35 USC § 112, ⁽|| 6.

[0091] Embora a presente invenção tenha sido descrita em

Petição 870190110896, de 30/10/2019, pág. 46/92 / 39 consideráveis detalhes com referência a determinadas versões preferidas dela, outras versões são possíveis. Por conseguinte, o espírito e escopo das reivindicações anexas não devem ser limitados à descrição das versões preferidas aqui contidas.

[0092] A atenção do leitor é direcionada a todos os papéis e documentos que são depositados concorrentemente com esta especificação e que estão abertas à inspeção pública com esta especificação, e o conteúdo de todos tais papéis e documentos aqui incorporados por referência.

[0093] Todos os recursos divulgados nesta especificação (incluindo qualquer reivindicações, resumo e desenhos anexos) podem ser substituídos por recursos alternativos servindo à propósito iguais, equivalentes ou similares, ao menos que expressamente colocado de outra forma. Assim sendo, ao menos que expressamente colocado de outra forma, cada característica divulgada é um exemplo somente de uma série genérica de equivalentes ou recursos similares.

Claims

REIVINDICAÇÕES

1. Método para tratar entrada ou saída (I/O) para ou do um ou mais dispositivos de armazenamento/de mídia (115, 118), em um sistema (100) tendo uma ou mais unidade de processador (105A, 105B), uma memória (106), e um ou mais dispositivos de armazenamento/de mídia, caracterizado pelo fato de compreender:

a) receber uma solicitação de I/O entrante proveniente de uma aplicação sendo executada no processador para transferir dados para ou receber dados de um ou mais dispositivos de armazenamento/de mídia;

b) criar uma estrutura em árvore incluindo instruções (101) executáveis pelo processador e embutida na memória que define uma ou mais camadas de processamento associadas com a solicitação de I/O, em que as instruções dividem os dados na solicitação de I/O em um ou mais agrupamentos de dados em cada uma das uma ou mais camadas de processamento, em que cada instrução de uma ou mais das camadas tem uma dependência de dados associada a uma ou mais correspondentes instruções em uma camada anterior, em que a dependência de dados para uma dada instrução permite a dada instrução para executar somente após execução de uma correspondente uma ou mais instruções dependentes na camada anterior;

c) classificar as instruções na estrutura em árvore em uma ordem de processamento determinando uma localização de cada agrupamento e dependência de dados entre agrupamentos de dados de diferentes camadas de processamento;

d) inserir uma ou mais instruções da estrutura em árvore em uma programação embutida na memória, em que uma posição de uma ou mais instruções dentro da programação depende de pelo menos, parcialmente da ordem de processamento; e

e) atender a solicitação de I/O executando as instruções de acordo com a programação com o processador, em que as instruções são

Petição 870190110896, de 30/10/2019, pág. 48/92
2 / 9 executadas pelo processador de acordo com a ordem de processamento associada com a estrutura em árvore embutida na memória.

2. Método de acordo com a reivindicação 1, caracterizado pelo fato de que:

os agrupamentos de dados associados com uma particular camada de processamento têm um tamanho diferente do que os agrupamentos de dados associados com uma outra camada de processamento; ou a estrutura em árvore inclui uma camada mais inferior, onde uma ou mais instruções da camada mais inferior tem uma associada dependência de dados para uma diferente instrução na camada mais inferior, em que a dependência de dados para uma dada instrução na camada mais inferior permite executar a dada instrução somente após execução de uma correspondente uma ou mais instruções dependentes na camada mais inferior.
3. Método de acordo com a reivindicação 1, caracterizado pelo fato de que:

e) inclui determinar se execução de uma instrução dependente está completada antes de executar uma dada instrução tendo uma dependência de dados; ou

e) inclui executar duas ou mais instruções a partir de uma camada de processamento comum em paralelo; ou

e) inclui executar duas ou mais instruções a partir de duas ou mais diferentes camadas de processamento em paralelo; ou

e) inclui intercalar execução pelo processador de uma ou mais instruções de uma ou mais outras solicitações de I/O dentre execução das instruções da estrutura em árvore; ou

e) inclui executar as uma ou mais instruções a partir das uma ou mais outras solicitações de I/O em paralelo com a execução de um ou mais instrução da estrutura em árvore; ou

e) inclui intercalação de duas ou mais solicitações de I/O,

Petição 870190110896, de 30/10/2019, pág. 49/92

3 / 9 quando as estruturas em árvore associadas com as duas ou mais solicitações de I/O encontram um valor de sobreposição limite, antes da inserção na programação; ou

e) inclui aplicar um patch diferencial para um ou mais arquivos em tempo de execução.
4. Método de acordo com a reivindicação 1, caracterizado pelo fato de que:

a uma ou mais camadas de processamento inclui uma camada de desarquivamento ou arquivamento; ou uma ou mais camadas de processamento inclui(incluem) uma camada de descriptografia ou camada de criptografia; ou a uma ou mais camadas de processamento inclui uma camada de descompressão ou de compressão; ou inserção da solicitação de I/O entrante dentro da programação em d) depende adicionalmente da restrição de prioridade associada com a solicitação de I/O; ou inserção da solicitação de I/O entrante dentro da programação em d) depende adicionalmente de uma restrição de prazo associada com a solicitação de I/O.
5. Sistema (100) para tratar entrada/saída (I/O), caracterizado pelo fato de compreender:

- uma unidade de processador (105A, 105B);

- uma memória (106) acoplada à unidade de processador;

- um ou mais dispositivos de armazenamento/de mídia (115, 118) acoplada com a unidade de processador; e

- um conjunto de instruções executáveis pelo processador (101) embutido na memória, as instruções sendo configuradas, quando executadas, para implementar um método para tratar entrada ou saída (I/O) para ou do um ou mais dispositivos de armazenamento/de mídia, o método

Petição 870190110896, de 30/10/2019, pág. 50/92

4 / 9 compreendendo:

a) receber uma solicitação de I/O entrante de uma aplicação sendo executada no processador para transferir dados para ou receber dados do um ou mais dispositivos de armazenamento/de mídia;

b) criar uma estrutura em árvore incluindo instruções executáveis pelo processador e embutido na memória que define uma ou mais camadas de processamento associadas com a solicitação de I/O, onde as instruções dividem os dados na solicitação de I/O em um ou mais agrupamentos de dados em cada um da uma ou mais camadas de processamento, em que cada instrução em uma ou mais das camadas tem uma associada dependência de dados para uma ou mais correspondentes instruções em uma camada anterior, em que a dependência de dados para uma dada instrução permite executar a dada instrução somente após execução de uma correspondente uma ou mais dependentes instruções na camada anterior;

c) classificar as instruções na estrutura em árvore em uma ordem de processamento determinando uma localização de cada agrupamento de dados e dependências de dados entre agrupamentos de dados das diferentes camadas de processamento;

d) inserir uma ou mais instruções da estrutura em árvore em uma programação embutida na memória, onde a posição de uma ou mais instruções dentro de uma programação depende pelo menos, parcialmente na ordem de processamento; e

e) atendendo a solicitação de I/O executando as instruções de acordo com a programação com o processador, em que as instruções são executadas pelo processador de acordo com a ordem de processamento associada com a estrutura em árvore embutida na memória.
6. Sistema de acordo com a reivindicação 5 caracterizado pelo fato de que:

os agrupamentos de dados associados com uma particular

Petição 870190110896, de 30/10/2019, pág. 51/92

5 / 9 camada de processamento têm um diferente tamanho do que os agrupamentos de dados associados com uma outra camada de processamento; ou a estrutura em árvore inclui uma camada mais inferior, onde uma ou mais instruções da camada mais inferior têm um associada dependência de dados para uma diferente instrução na camada mais inferior, em que a dependência de dados para uma dada instrução na camada mais inferior permite executar a dada instrução somente após a execução da corresponde uma ou mais dependentes instruções na camada mais inferior.
7. Sistema de acordo com a reivindicação 5, caracterizado pelo fato de que:

e) inclui determinar se a execução da instrução dependente está completa antes de executar uma dada instrução tendo uma dependência de dados; ou

e) inclui executar duas ou mais instruções de uma camada de processsamento comum em paralelo; ou

e) inclui executar duas ou mais instruções a partir de duas ou mais diferentes camadas de processamento em paralelo; ou

e) inclui intercalar a execução pelo processador de uma ou mais instruções a partir de uma ou mais outras solicitações de I/O dentre a execução das instruções da estrutura em árvore; ou

e) inclui intercalar a execução pelo processador de uma ou mais instruções a partir de uma ou mais outras solicitações de I/O dentre a execução das instruções da estrutura em árvore, e em que e) inclui executar a uma ou mais instruções a partir da uma ou mais outras solicitações de I/O em paralelo com a execução de uma ou mais instruções da estrutura em árvore.
8. Sistema de acordo com a reivindicação 5, caracterizado pelo fato de que:

a uma ou mais camadas de processamento inclui uma camada de arquivamento ou desarquivamento; ou

Petição 870190110896, de 30/10/2019, pág. 52/92

6 / 9 uma ou mais camadas de processamento inclui(incluem) uma camada de descriptografia ou camada de criptografia; ou a uma ou mais camadas de processamento inclui uma camada de descompressão ou de compressão; ou inserção da solicitação de I/O entrante dentro da programação em d) depende adicionalmente da restrição de prioridade associada com a solicitação de I/O; ou inserção da solicitação de I/O entrante dentro da programação em d) depende adicionalmente de uma restrição de prazo associada com a solicitação de I/O.
9. Sistema de acordo com a reivindicação 5, caracterizado pelo fato de que:

e) inclui intercalação de duas ou mais solicitações de I/O, quando as estruturas em árvore associadas com as duas ou mais solicitações de I/O encontram um valor de sobreposição limite, antes da inserção na programação; ou

e) inclui aplicar um patch diferencial para um ou mais arquivos em tempo de execução.
10. Meio de armazenamento legível por computador, caracterizado pelo fato de compreender instruções legíveis por computador gravados no mesmo que, quando executadas por um computador, fazem com que o computador trate entrada ou saída (I/O) para ou de um ou mais dispositivos de armazenamento/de mídia (115, 118), o computador executando as seguintes etapas:

a) receber uma solicitação de I/O entrante de uma aplicação sendo executada no processador para transferir dados para ou receber dados do um ou mais dispositivos de armazenamento/de mídia;

b) criar uma estrutura em árvore incluindo instruções executáveis pelo processador e embutida na memória que define uma ou mais

Petição 870190110896, de 30/10/2019, pág. 53/92

7 / 9 camadas de processamento associadas com a solicitação de I/O, em que as instruções dividem os dados na solicitação de I/O em um ou mais agrupamentos de dados em cada uma das uma ou mais camadas de processamento, em que cada instrução de uma ou mais das camadas tem uma dependência de dados associada a uma ou mais correspondentes instruções em uma camada anterior, em que a dependência de dados para uma dada instrução permite a dada instrução para executar somente após execução de uma correspondente uma ou mais instruções dependentes na camada anterior;

c) classificar as instruções na estrutura em árvore em uma ordem de processamento determinando uma localização de cada agrupamento de dados e dependência de dados entre agrupamentos de dados de diferentes camadas de processamento;

d) inserir uma ou mais instruções da estrutura em árvore em uma programação embutida na memória, em que uma posição da ou mais instruções dentro da programação depende de pelo menos, parcialmente da ordem de processamento; e

e) atender à solicitação de I/O executando as instruções de acordo com a programação com o processador, onde as instruções são executadas pelo processador de acordo com a ordem de processamento associada com a estrutura em árvore embutida na memória.
11. Meio de armazenamento legível por computador, de acordo com a reivindicação 10, caracterizado pelo fato de que:

os agrupamentos de dados associados com uma particular camada de processamento têm um tamanho diferente do que os agrupamentos de dados associados com uma outra camada de processamento; ou em que a estrutura em árvore inclui uma camada mais inferior, em que uma ou mais instruções da camada mais inferior tem uma associada dependência de dados para uma diferente instrução na camada mais inferior, em que a dependência de dados para uma dada instrução na

Petição 870190110896, de 30/10/2019, pág. 54/92

8 / 9 camada mais inferior permite executar a dada instrução somente após execução de uma correspondente uma ou mais instruções dependentes na camada mais inferior; ou

e) inclui intercalar execução pelo processador de uma ou mais instruções de uma ou mais outras solicitações de I/O dentre execução das instruções da estrutura em árvore.
12. Meio de armazenamento legível por computador, de acordo com a reivindicação 10, caracterizado pelo fato de que:

e) inclui determinar se execução de uma instrução dependente está completada antes de executar uma dada instrução tendo uma dependência de dados; ou

e) inclui executar duas ou mais instruções a partir de uma camada de processamento comum em paralelo; ou

e) inclui executar duas ou mais instruções a partir de duas ou mais diferentes camadas de processamento em paralelo; ou

e) inclui intercalar execução pelo processador de uma ou mais instruções de uma ou mais outras solicitações de I/O dentre execução das instruções da estrutura em árvore, e em que e) inclui executar a uma ou mais instruções da uma ou mais outras solicitações de I/O em paralelo com a execução de uma ou mais instruções da estrutura em árvore.
13. Meio de armazenamento legível por computador, de acordo com a reivindicação 10, caracterizado pelo fato de que:

a uma ou mais camadas de processamento inclui uma camada de desarquivamento ou arquivamento; ou a uma ou mais camadas de processamento inclui(incluem) uma camada de descriptografia ou camada de criptografia; ou a uma ou mais camadas de processamento inclui uma camada de descompressão ou compressão.
14. Meio de armazenamento legível por computador, de

Petição 870190110896, de 30/10/2019, pág. 55/92

9 / 9 acordo com a reivindicação 10, caracterizado pelo fato de que inserção da solicitação de I/O entrante dentro da programação em e) depende adicionalmente de uma restrição de prazo associada com a solicitação de I/O.
15. Meio de armazenamento legível por computador, de acordo com a reivindicação 10, caracterizado pelo fato de que:

e) inclui intercalar duas ou mais solicitações de I/O, quando as estruturas em árvore associadas com as duas ou mais solicitações de I/O encontram um valor de sobreposição limite, antes da inserção na programação; ou

e) inclui aplicar um patch diferencial para um ou mais arquivos em tempo de execução.